import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 30
 * Time: 21:31
 */
//牛客 重建二叉树
public class Solution5 {
    //法一
    static int i = 0;
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {

        return reConstructBinaryTreeF (preOrder, vinOrder, 0, vinOrder.length - 1);//在vinOrder数组0到vinOrder.length-1下标中找preOrder数组中的某个元素
    }
    public TreeNode reConstructBinaryTreeF (int[] preOrder, int[] vinOrder, int ib, int ie) {
        if(ib > ie) return null;//若数组没有元素则返回null
        TreeNode root = new TreeNode(preOrder[i]);
        int mid = find(vinOrder, preOrder[i], ie);
        i++;
        root.left = reConstructBinaryTreeF (preOrder, vinOrder, ib, mid - 1);
        root.right = reConstructBinaryTreeF (preOrder, vinOrder, mid + 1, ie);
        return root;
    }
    public int find(int[] vinOrder, int k, int ie) {
        for (int i = 0; i <= ie ; i++) {
            if(vinOrder[i] == k) {
                return i;
            }
        }
        return -1;
    }




    //法二 官方推荐方法
    public static TreeNode reConstructBinaryTree1 (int[] preOrder, int[] vinOrder) {
        int j = 0;
        if(preOrder.length == 0) return null;
        while (preOrder[0] != vinOrder[j]) {
            j++;
        }
        TreeNode root = new TreeNode(preOrder[0]);//前序遍历的各个子序列的头结点就是根节点
        root.left = reConstructBinaryTree1 (Arrays.copyOfRange(preOrder, 1, j + 1), Arrays.copyOfRange(vinOrder, 0, j));
        root.right = reConstructBinaryTree1 (Arrays.copyOfRange(preOrder, j + 1, preOrder.length), Arrays.copyOfRange(vinOrder, j + 1, vinOrder.length));
        return root;
    }



    //法三 官方方法
    public TreeNode reConstructBinaryTree2(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}
